#pragma once
#include<vector>
#include<list>
#include<set>
#include<iostream>
#include<unordered_set>
#include<unordered_map>

using namespace std;

//开散列——哈希桶的哈希表
namespace hash_bucket
{
//哈希表存储的数据类型
template<class T>
struct HashNode
{
    HashNode* next;//节点指针
    T _data;
    
    HashNode(const T& data):_data(data)
    ,next(nullptr)
    {}
};

//仿函数
template<class K>
struct HashFunc
{
  size_t operator()(const K& key)
    {
      return (size_t)key;
  }
};

//为了实现，在插入string类型时，不需要手动的传入仿函数，我们可以对仿函数进行特化
template<>
struct HashFunc<string>
{
  size_t operator()(const string& key)
    {
      size_t hash=0;
      for(auto e:key)
      {
          hash+=e;//这里还是有缺陷，如果插入的字符串“abc”和“acb”，他们转出的整形值都是一样的
          hash*=31;//这里就是为了解决这种冲突，但只是减少冲突，冲突永远存在，因为整形的值是有限的，但是字符串的可能性无穷多
      }
      return hash;
  }
};

//迭代器

template<class K,class T,class KeyOfT,class Hash>
class HashTable;
template<class K1,class T1,class Ref,class Ptr ,class KeyOfT1,class Hash1>//之所以K1、T1...因为声明为友员类时，模版参数相同会导致二义性的出现
class _iterator
{
public:
    typedef HashNode<T1> Node;
    typedef _iterator<K1,T1,Ref,Ptr,KeyOfT1,Hash1> self;
    
    
    _iterator(Node* node,HashTable<K1, T1, KeyOfT1, Hash1>* pht,size_t hashi)
    :_node(node),_pht(pht),_hashi(hashi)
    {
        
    }
    
    _iterator(Node* node,const HashTable<K1, T1, KeyOfT1, Hash1>* pht,size_t hashi)
    :_node(node),_pht(pht),_hashi(hashi)
    {
        
    }
    Node* _node;
    const HashTable<K1,T1,KeyOfT1,Hash1>* _pht;
    size_t _hashi;//作为一个标识
    
    
    
    
    self& operator++()
    {
        if(_node->next)
        {
            //如果当前桶还有节点，走到下一个节点
            _node=_node->next;
        }
        else
        {
            //如果当前桶走完了，我们需要找下一个桶
//            KeyOfT kot;
//            Hash hf;
//            size_t hashi=hf(kot(_node->_data))%_pht._tables.size();
            
            ++_hashi;
            while(_hashi<_pht->_tables.size())
            {
                if(_pht->_tables[_hashi])
                {
                    _node=_pht->_tables[_hashi];
                    break;
                }
                ++_hashi;
            }
            
            if(_hashi==_pht->_tables.size())
            {
                _node=nullptr;
            }
            
        }
        return *this;
    }
    
    Ref operator*()
    {
        return _node->_data;
    }
    
    Ptr operator->()
    {
        return &_node->_data;
    }
    
    
    bool operator!=(const self&s)
    {
        return _node!=s._node;
    }
    
    bool operator==(const self&s)
    {
        return _node==s._node;
    }
};


template<class K,class T,class KeyOfT,class Hash>
class HashTable
{
    template<class K1,class T1,class Ref,class Ptr ,class KeyOfT1,class Hash1>
    friend class _iterator;
    
    typedef HashNode<T> Node;
public:
    typedef _iterator<K, T, T&,T* ,KeyOfT,Hash> iterator;
    typedef _iterator<K, T, const T&,const T* ,KeyOfT,Hash> const_iterator;
    
    iterator begin()
    {
        for(size_t i=0;i<_tables.size();i++)
        {
            if(_tables[i])
                return iterator(_tables[i],this,i);//this就是当前哈希表的指针
        }
        return end();
    }
    
    iterator end()
    {
        return iterator(nullptr,this,-1);
    }
    
    //this:const HashTable<...>
    const_iterator begin() const
    {
        for(size_t i=0;i<_tables.size();i++)
        {
            if(_tables[i])
                return const_iterator(_tables[i],this,i);//this就是当前哈希表的指针
        }
        return end();
    }
    
    const_iterator end() const
    {
        return const_iterator(nullptr,this,-1);
    }
    
    HashTable()
    {
        _tables.resize(10);
    }
    
    ~HashTable()//对链表进行释放
    {
        for(size_t i=0;i<_tables.size();i++)
        {
            Node* cur=_tables[i];
            while(cur)
            {
                Node* next=cur->next;//释放一个节点的时候一定要记住，要保留下一个节点的地址
                delete cur;
                cur=next;
            }
            _tables[i]=nullptr;//释放完，需要对哈希表的数据置空
        }
    }
    
    pair<iterator, bool> Insert(const T& data)
    {
        Hash hf;//仿函数
        KeyOfT kot;//仿函数
        
        iterator it=Find(kot(data));
        if(it!=end())
            return make_pair(it, false);
    
        //负载因子,这里的负载因子最大可以为一
       if(_n==_tables.size())
        //if(_n*10/_tables.size()==7)
        {
            //这里的扩容，不能像开散列那样，因为那样是两个vector类型进行交换，释放资源，是由内部决定的，而现在，除了释放vector还要释放链表，所以这里得手动释放
            vector<Node*> newTables;//创建一个新的哈希表
            newTables.resize(_tables.size()*2,nullptr);//新的哈希表扩容到原来的2倍
            //遍历旧表
            for(size_t i=0;i<_tables.size();i++)
            {
                Node* cur =_tables[i];
                while(cur)
                {
                    Node* next=cur->next;//记录头节点的下一个位置
                    
                    //挪动到映射的新表，按照新的映射关系，将旧表数据放到新表中，这里采用的方法：对原来旧表的节点，改变他们的指向，连接到新表中，这样做可以减少空间浪费
                    size_t hashi=hf(kot(cur->_data))%newTables.size();//hf(kot(cur->_data))内部彷函数是把关键字取出来，外层放函数是把关键字不是整形的，转成整形
                    cur->next=newTables[hashi];
                    newTables[hashi]=cur;
                    
                    cur=next;//遍历一个桶的数据
                }
                _tables[i]=nullptr;//一定要置空，不然出了作用域，新表会调用析构函数，对原来数据进行释放
            }
            _tables.swap(newTables);//新表和旧表交换数据
        }
        
        size_t hashi=hf(kot(data))%_tables.size();//将关键字和哈希表建立映射
        Node* newnode=new Node(data);//创建的节点
        
        //头插
        newnode->next=_tables[hashi];
        _tables[hashi]=newnode;
        ++_n;//关键字数据+1
        
        return make_pair(iterator(newnode,this,hashi), true);
    }
     iterator Find(const K& key)
    {
        Hash hf;//仿函数
        KeyOfT kot;
        size_t hashi=hf(key)%_tables.size();
        Node* cur=_tables[hashi];
        while(cur)
        {
            if(kot(cur->_data)==key)
            {
                return iterator(cur,this,hashi);
            }
            cur=cur->next;
        }
        return end();
    }
    
    bool Erase(const K& key)
    {
        size_t hashi=key%_tables.size();
        Node* cur=_tables[hashi];
        Node* parent=nullptr;
        while(cur)
        {
            if (kot(cur->_data)== key)
            {
                if (parent == nullptr)//删除的头节点
                {
                    _tables[hashi] = cur->next;
                }
                else
                {
                    parent->next = cur->next;
                }
                delete cur;

                return true;
            }

            parent = cur;//在一个桶里循环查找
            cur = cur->next;
        }
        return false;
    }
    void Print()
    {
        KeyOfT kot;
        for(size_t i=0;i<_tables.size();i++)
        {
            Node* cur=_tables[i];
            while(cur)
            {
                cout<<"["<<i<<"]->"<<kot(cur->_data)<<endl;
                cur=cur->next;
            }
        }
    }
    size_t size()
    {
        return _n;
    }
    
    void Some()//哈希桶的结构描述
            {
                size_t bucketSize = 0;//使用桶的个数
                size_t maxBucketLen = 0;//桶的最大长度
                size_t sum = 0;//插入数据的个数
                double averageBucketLen = 0;//平均桶长度

                for (size_t i = 0; i < _tables.size(); i++)
                {
                    Node* cur = _tables[i];
                    if (cur)
                    {
                        ++bucketSize;
                    }

                    size_t bucketLen = 0;
                    while (cur)
                    {
                        ++bucketLen;
                        cur = cur->next;
                    }

                    sum += bucketLen;

                    if (bucketLen > maxBucketLen)
                    {
                        maxBucketLen = bucketLen;
                    }
                }

                averageBucketLen = (double)sum / (double)bucketSize;

        printf("all bucketSize:%lu\n", _tables.size());
                printf("bucketSize:%lu\n", bucketSize);
                printf("maxBucketLen:%lu\n", maxBucketLen);
                printf("averageBucketLen:%lf\n\n", averageBucketLen);
            }
private:
    vector<Node*> _tables;//哈希表外层使用的顺序表
    size_t _n;//关键字的个数
};

}
